class Solution(object):
    def makesquare(self, matchsticks):
        total = sum(matchsticks)
        if total % 4 != 0:
            return False

        side = total // 4
        matchsticks.sort(reverse=True)
        edges = [0] * 4

        def backtrack(index):
            if index == len(matchsticks):
                return all(e == side for e in edges)
            for i in range(4):
                if edges[i] + matchsticks[index] > side:
                    continue
                if i > 0 and edges[i] == edges[i - 1]:
                    continue
                edges[i] += matchsticks[index]
                if backtrack(index + 1):
                    return True
                edges[i] -= matchsticks[index]
            return False

        return backtrack(0)
